import java.util.ArrayDeque;
import java.util.Queue;
import java.util.*;

/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-05-07
 * Time:13:45
 */
public class 最小基因变化 {
    public int minMutation(String start, String end, String[] bank) {
        char[] arr = {'A','C','G','T'};
        Set<String> set = new HashSet<>();
        for(int i = 0;i < bank.length;i++) {
            set.add(bank[i]);
        }
        Set<String> isUsed = new HashSet<>();
        if(start.equals(end)) {
            return 0;
        }
        if(!set.contains(end)) {
            return -1;
        }
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(start);
        isUsed.add(start);
        int count = 1;
        while(!queue.isEmpty()) {
            int len = queue.size();
            for(int i = 0;i < len;i++) {
                String str = queue.poll();
                for(int j =0;j < 8;j++) {
                    for(int k = 0;k < 4;k++) {
                        if(arr[k] != str.charAt(j)) {
                            StringBuffer sb = new StringBuffer(str);
                            sb.setCharAt(j,arr[k]);
                            String str2 = sb.toString();
                            if(!isUsed.contains(str2) && set.contains(str2)) {
                                if(str2.equals(end)) {
                                    return count;
                                }
                                queue.offer(str2);
                                isUsed.add(str2);
                            }
                        }
                    }
                }
            }
            count++;
        }
        return -1;
    }
}
